import Utils.SortUtils;
import org.omg.PortableInterceptor.SUCCESSFUL;

/**
 * 快速排序(先切分再排序)
 * @author xiaolu
 * @version 1.0
 * @date 2020/6/3 18:04
 */
public class Quick {

    public static void sort(Comparable[] a){

        sort(a, 0, a.length-1);
    }

    public static void sort(Comparable[] a, int lo, int hi){

        if (hi <= lo) return;
        int j = partition(a, lo , hi);
        sort(a , lo , j-1);
        sort(a , j+1 , hi);
    }

    // 快速排序的切分
    private static int partition(Comparable[] a, int lo, int hi){

        int i = lo;
        int j = hi+1;
        Comparable v = a[lo]; // 切分元素
        while (true){
            while (SortUtils.less(a[++i], v)) if (i == hi) break;
            while (SortUtils.less(v, a[--j])) if (j == lo) break;
            if (i >= j) break;
            SortUtils.exch(a, i, j);
        }
        SortUtils.exch(a, lo, j); // 将v放在正确的位置
        return j;
    }

    public static void main(String[] args) {

        // 测试排序算法
        Integer[] a = {4, 23, 6, 78, 1, 54, 231, 9, 12};
        // Integer[] a = {1, 5, 6, 4, 343, 234};
        sort(a);
        assert SortUtils.isSorted(a);
        SortUtils.show(a);
    }
}
